package ex.algorithms.sorting;

public class CountingSort {
	public static int[] sortIncreasing(int[] input, int maxElement) {
		if(input == null || input.length < 2)
			return input;
		
		int[] output = new int[input.length];
		int[] counter = new int[maxElement + 1];
		
		for(int i=0; i<counter.length; i++)
			counter[i] = 0;
		
		for(int i=0; i<input.length; i++)
			counter[input[i]] += 1;
		
		for(int i=1; i<counter.length; i++)
			counter[i] += counter[i-1];
		
		for(int i=input.length-1; i>=0; i--) {
			int pos = counter[input[i]];
			output[pos-1] = input[i];
			counter[input[i]] -= 1;
		}
		
		return output;
	}
}
